package com.tianyuan.test3;

/**
 * 链表中的节点每k个一组翻转
 *
 * @date 2025/10/15 18:51
 * 将给出的链表中的节点每 k个一组翻转，返回翻转后的链表
 * 如果链表中的节点数不是 k的倍数，将最后剩下的节点保持原样
 * 你不能更改节点中的值，只能更改节点本身。
 *
 * 数据范围：0≤n≤2000，1≤k≤2000，链表中每个元素都满足 0≤val≤1000
 * 要求空间复杂度O(1)，时间复杂度O(n)
 * 例如：
 * 给定的链表是1→2→3→4→5
 * 对于k=2，你应该返回2→1→4→3→5
 * 对于k=3，你应该返回3→2→1→4→5
 */
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // 边界处理：如果链表为空，直接返回
        if(head == null){
            return head;
        }

        // 存储链表中所有节点的值
        ArrayList<Integer> list = new ArrayList<>();
        // 用于临时存储k个节点的值，实现翻转功能
        Stack<Integer> stack = new Stack<>();
        // 临时指针，用于遍历原链表
        ListNode tmpList = head;

        // 遍历原链表，将所有节点的值存入list集合
        while(tmpList != null){
            list.add(tmpList.val);
            tmpList = tmpList.next;
        }
        // 如果k大于链表长度，无需翻转，直接返回原链表
        if(k > list.size()){
            return head;
        }

        // 存储处理后的结果（翻转后的节点值序列）
        ArrayList<Integer> result = new ArrayList<>();

        // 遍历所有节点值，每k个一组进行翻转
        for(int i = 0; i < list.size(); i++){
            // 将当前节点值入栈
            stack.push(list.get(i));
            // 当累计到k个节点时（i从0开始，所以i+1表示当前已处理的节点数）
            if((i + 1) % k == 0){
                // 将栈中元素弹出并加入结果集（实现翻转效果）
                while(!stack.isEmpty()){
                    result.add(stack.pop());
                }
            }
        }

        // 处理剩余不足k个的节点（这些节点不需要翻转）
        ArrayList<Integer> tmp = new ArrayList<>();
        // 将栈中剩余元素弹出（此时顺序是反的）
        while(!stack.isEmpty()){
            tmp.add(stack.pop());
        }
        // 反转临时列表，恢复剩余节点的原始顺序
        Collections.reverse(tmp);
        // 将剩余节点加入结果集
        result.addAll(tmp);


        // 根据处理后的结果集重新构建链表
        // 创建新链表的第一个节点
        ListNode tmpNode = new ListNode(result.get(0));
        // 保存新链表的头节点，用于返回
        ListNode returnList = tmpNode;

        // 依次创建剩余节点并连接成链表
        for(int i = 1; i < result.size(); i++){
            ListNode node = new ListNode(result.get(i));
            tmpNode.next = node;
            tmpNode = tmpNode.next;
        }

        // 返回新链表的头节点
        return returnList;
    }






    public static void main(String[] args) {
        Solution solution = new Solution();

        // 构建测试链表: 1→2→3→4→5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // 测试k=2的情况
        ListNode resultK2 = solution.reverseKGroup(copyList(head), 2);
        System.out.print("k=2时的结果: ");
        printList(resultK2);

        // 测试k=3的情况
        ListNode resultK3 = solution.reverseKGroup(copyList(head), 3);
        System.out.print("k=3时的结果: ");
        printList(resultK3);
    }

    // 辅助方法: 复制链表，避免原链表被修改
    private static ListNode copyList(ListNode head) {
        if (head == null) return null;
        ListNode newHead = new ListNode(head.val);
        ListNode current = newHead;
        while (head.next != null) {
            head = head.next;
            current.next = new ListNode(head.val);
            current = current.next;
        }
        return newHead;
    }

    // 辅助方法: 打印链表
    private static void printList(ListNode head) {
        List<Integer> values = new ArrayList<>();
        while (head != null) {
            values.add(head.val);
            head = head.next;
        }
        System.out.println(values);
    }
}